package leetcode.code1110;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import leetcode.helper.tree.TreeNode;

public class Solution {

	List<TreeNode> ans;
	Set<Integer> delete;

	public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
		this.delete = new HashSet<>();
		Arrays.stream(to_delete).forEach(i -> this.delete.add(i));
		ans = new ArrayList<>();
		this.f(root, true);
		return ans;
	}

	private void f(TreeNode root, boolean is) {
		if (root == null) {
			return;
		}
		if (!this.delete.contains(root.val)) {
			if (is)
				this.ans.add(root);
			if (root.left != null && this.delete.contains(root.left.val)) {
				this.f(root.left.left, true);
				this.f(root.left.right, true);
				root.left = null;
			} else {
				this.f(root.left, false);
			}
			if (root.right != null && this.delete.contains(root.right.val)) {
				this.f(root.right.left, true);
				this.f(root.right.right, true);
				root.right = null;
			} else {
				this.f(root.right, false);
			}
		} else {
			this.f(root.left, true);
			this.f(root.right, true);
		}

	}

}
